// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include <time.h>
//
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// // 队列节点结构
// typedef struct QueueNode {
//     TreeNode* data; // 存储数据
//     struct QueueNode* next; // 指向下一个节点
// } QueueNode;
//
// // 队列结构
// typedef struct {
//     QueueNode* front; // 队头指针
//     QueueNode* rear;  // 队尾指针
// } LinkQueue;
//
// void InitQueue(LinkQueue* q) {
//     q->front=q->rear=NULL;
// }
//
// void Enqueue(LinkQueue* q,TreeNode* x){
//     QueueNode* newNode=(QueueNode*)malloc(sizeof(QueueNode));
//     if(newNode==NULL) {
//         exit(1);
//     }
//     newNode->data=x;
//     newNode->next=NULL;
//
//     if(q->front==NULL&&q->rear==NULL) {
//         q->front=q->rear=newNode;
//     }else {
//         q->rear->next=newNode;
//         q->rear=q->rear->next;
//     }
// }
//
// TreeNode* Dequeue(LinkQueue* q) {
//     if(q->front==NULL) {
//         return NULL;
//     }
//     QueueNode* tmp=q->front;
//     q->front=q->front->next;
//     TreeNode* node=tmp->data;
//     if(q->front==NULL) {
//         q->rear=NULL;//必须要这步
//     }
//     free(tmp);
//     return node;
// }
//
// void LeverOrder(TreeNode* root) {
//     if(root==NULL) {
//         return;
//     }
//     LinkQueue q;
//     InitQueue(&q);
//     Enqueue(&q,root);
//     while (q.front!=NULL) {
//         TreeNode* p=Dequeue(&q);
//         printf("%d ",p->value);
//         if(p->left)Enqueue(&q,p->left);
//         if(p->right)Enqueue(&q,p->right);
//     }
//     printf("\n");
// }
//
// // 创建新节点
// TreeNode* CreateNode(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) exit(0);
//     newNode->value = value;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入节点（二叉搜索树规则）
// TreeNode* InsertNode(TreeNode* root, DataType x) {
//     if (root == NULL) {
//         return CreateNode(x);
//     }
//     if (x < root->value) {
//         root->left = InsertNode(root->left, x);
//     } else {
//         root->right = InsertNode(root->right, x);
//     }
//     return root;
// }
//
// // 释放内存
// void FreeTree(TreeNode* root) {
//     if (root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// //左右节点交换
// void ExchangeGGG(TreeNode* root) {
//     if(root) {
//         ExchangeGGG(root->left);
//         ExchangeGGG(root->right);
//         TreeNode* tmp=root->left;
//         root->left=root->right;
//         root->right=tmp;
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int value[] = {50, 30, 70, 20, 40, 60, 80};
//     int length = sizeof(value) / sizeof(value[0]);
//
//     // 构建二叉搜索树
//     for (int i = 0; i < length; i++) {
//         root = InsertNode(root, value[i]);
//     }
//
//     LeverOrder(root);
//     ExchangeGGG(root);
//     LeverOrder(root);
//
//     FreeTree(root);
//     return 0;
// }